package com.cet.qz.unit01.chapter1_1;

import edu.princeton.cs.algs4.StdIn;

/**
 * @program: algorithm
 * @description: 编写一段程序，创建一个N×N 的布尔数组a[][]。其中当i 和j 互质时（没有相同因子），a[i][j] 为true，否则为false。
 * @author: 陈恩涛
 * @create: 2020-12-18 17:32
 **/
public class Qz1_1_30 {

    /*
     *方法描述： 欧几里德算法求最大公约数
     *
     * @param p
     * @param q
     * @return int
     * @author chenentao
     * @date 2020/12/18 18:20
     */
    public static int gcd(int p, int q) {
        if(q == 0)
            return p;
        int r = p % q;
        return gcd(q,r);
    }

    /*
     *方法描述： 判断两个自然数是否互质
     *
     * @param a
     * @param b
     * @return boolean
     * @author chenentao
     * @date 2020/12/18 18:20
     */
    public static boolean ArePrimeNumbers(int a,int b){
        if(a == 1 && b == 1)
            return true;
        else if(a <= 0 || b <= 0 || a == b)//这里已经排除了1,1了，两个相同的自然数，除了1,1都不互质
            return false;
        else if(a == 1 || b == 1)
            return true;
        else{
            if(gcd(a,b) == 1)
                return true;
            else
                return false;
        }
    }

    /*
     *方法描述： 获取boolean数组'
     *
     * @param N
     * @return boolean[][]
     * @author chenentao
     * @date 2020/12/18 18:21
     */
    public static boolean[][] getBooleanArray(int N){
        boolean[][] booleanArr = new boolean[N][N];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                booleanArr[i][j] = ArePrimeNumbers(i+1,j+1);
            }
        }
        return booleanArr;
    }

    public static void main(String[] args) {
        int n = StdIn.readInt();
        boolean[][] booleanArray = getBooleanArray(n);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                System.out.print(booleanArray[i][j] + "\t");
            }
            System.out.print("\n");
        }
    }
}
